Найдите наименьшее общее кратное чисел \(\displaystyle 18\) и \(\displaystyle 45\), используя алгоритм Евклида и формулу
\(\displaystyle \text{НОК}(a,b)= \frac{a\cdot b}{\text{НОД}(a, b)}{\small .}\)
\(\displaystyle \text{НОК}(18, 45) = \frac{18\cdot 45}{\text{НОД}(18, 45)}=\)
Алгоритм Евклида для НОД(a, b)
1. Пусть \(\displaystyle b>a{\small .}\) Делим большее \(\displaystyle b\) на меньшее \(\displaystyle a\) с остатком:
\(\displaystyle b=a\cdot n+ {\bf r}{\small .}\)
2. \(\displaystyle \text{НОД}(a,b)=\text{НОД}(a,{\bf r}){\small .}\)
3. Если \(\displaystyle {\bf r}=0{\small ,}\) то \(\displaystyle \text{НОД}(a,{\bf r})=a{\small .}\) Если \(\displaystyle {\bf r}=\not 0{\small ,}\) то ищем \(\displaystyle \text{НОД}(a,{\bf r})\) (но теперь \(\displaystyle a>{\bf r}\)).
Если \(\displaystyle \text{НОД}(a, b)\) найден, то
\(\displaystyle \text{НОК}(a, b) = \frac{a\cdot b}{\text{НОД}(a, b)}{\small .}\)
Найдем \(\displaystyle \text{НОД}(18, 45){\small :}\)
Шаг 1. Применим алгоритм Евклида к \(\displaystyle \text{НОД}(18, 45){\small .}\)
1. Так как \(\displaystyle 45> 18{\small ,}\) то делим \(\displaystyle 45\) на \(\displaystyle 18\) с остатком: \(\displaystyle 45=18\cdot 2+{\bf 9}{\small .}\)
2. \(\displaystyle \text{НОД}(18, 45)=\text{НОД}(18,{\bf 9}){\small .}\)
3. Так как \(\displaystyle {\bf 9} =\not 0{\small ,}\) то переходим к шагу 2.
Шаг 2. Применим алгоритм Евклида к \(\displaystyle \text{НОД}(18, 9)=\text{НОД}(9, 18){\small .}\)
1. Так как \(\displaystyle 18> 9{\small ,}\) то делим \(\displaystyle 18\) на \(\displaystyle 9\) с остатком: \(\displaystyle 18=9\cdot 2+{\bf 0}{\small .}\)
2. \(\displaystyle \text{НОД}(9, 18)=\text{НОД}(9,{\bf 0}){\small .}\)
3. \(\displaystyle \text{НОД}(9,{\bf 0})=9{\small .}\)
Таким образом, \(\displaystyle \text{НОД}(18, 45)=9{\small .}\)
Найдем \(\displaystyle \text{НОК}(18, 45){\small :}\)
\(\displaystyle \text{НОК}(18, 45)= \frac{18\cdot 45}{\text{НОД}(18, 45)}=\frac{18\cdot 45}{9}=2\cdot 45=90{\small .}\)
Ответ: \(\displaystyle \text{НОК}(18, 45)=90{\small .}\)